package leetcode316;

import java.math.BigInteger;

/**
 * 这里补充一些知识：
 * 0 和  x 的最大公因数就是 x
 * 因为 0 除以 任何数  都是  0
 *
 *该题的 数据量  为  n = 10 ^ 3   O(N ^ 2) 是可以 过的
 *
 *attention：
 * 要求的 连续的  子数组数列 
 * 就是 暴力 枚举 ： 以  nums[0] 开头 满足 要求 的连续子数组 个数,以 nums[1] 开头的 满足的..
 * 以nums[2] 开头的 满足要求的 连续.....
 * 以nums[3] 开头的 .....
 */
public class Two {

	
	
	// arignote 的写法   : 他就是单纯 不想自己写  gcd 才用的  BigInteger 这个 类
	public int subarrayGCD(int[] nums, int k) {
		int count = 0;
		for (int i = 0; i < nums.length; i++) {
			BigInteger gcd = BigInteger.ZERO;
			for (int j = i; j < nums.length; j++) {
				count += (gcd = gcd.gcd(BigInteger.valueOf(nums[j]))).intValue() == k ? 1 : 0;
			}
		}
		return count;
	}
	
	
	
	
	/**
	 * 这个 分析的  过程确实值得学习一下
	 */
	public static int solution(int nums[],int k) {
		int count = 0;
		for(int i = 0;i < nums.length;i++) {
			// 做一个小小的剪枝
			if(nums[i] % k != 0)
				continue;
			int gcd = 0;
			for(int j = i;j < nums.length;j++) {
				// 这里也可以做剪枝 
//				if(nums[j] % k != 0)
				count += (gcd = gcd(gcd,nums[j])) == k ? 1 : 0;
			}
		}
		return count;
	}
	
	
	
	
	/**
	 * 辗转相除法
	 * 动手实现一下这个过程就 明白这整个的过程了
	 */
	public static int gcd(int a,int b) {
		return b == 0 ? a : gcd(b,a % b );
	}

	
	public static void main(String []args) {
		int a = 12;
		int b = 8;
		System.out.println(gcd(a,b));
	}
	
	
}
